A computer network is a collection of interconnected computing devices that can exchange data and share resources. In a packet-based network, the computing devices communicate data by dividing the data into small blocks called packets, which are individually routed across the network from a source device to a destination device. The destination device extracts the data from the packets and assembles the data into its original form. Dividing the data into packets enables the source device to resend only those individual packets that may be lost during transmission.
Network routers maintain routing information that describes available routes through the network. Upon receiving a packet, a router examines information within the packet and forwards the packet in accordance with the routing information. In order to maintain an accurate representation of the network, routers exchange routing information in accordance with one or more routing protocols, such as an interior gateway protocol (IGP) or Border Gateway Protocol (BGP).
Computer networks may have parallel data paths. For example, a network may have a number of interconnected intermediate devices that provide connectivity from an inbound edge router to an outbound edge router. In a conventional routed network, the inbound edge router makes routing decisions to forward traffic to the outbound edge router. Based on information within each packet and routing information learned by operation of routing protocols, the inbound edge router selects a neighboring “next hop” router and forwards the packet out on an outbound physical link coupling the router to the selected next hop router. For example, the inbound edge router may choose the lowest cost physical link when selecting the next hop. In some cases the inbound edge router attempts to load balance when forwarding packets to the next hop routers, i.e., the neighboring routers coupled to its outgoing physical links. As a result, some of the packets traveling between two locations may make use of one path, while other packets may make use of one or more alternate paths.